COMMENT ⊗   VALID 00003 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	.require "memo.pub[let,jmc]" source
C00009 00003	.skip 1
C00010 ENDMK
C⊗;
.require "memo.pub[let,jmc]" source;
.turn off "{"
.turn on "∂"
.cb ANOTHER SAMEFRINGE


	This SAMEFRINGE is simpler than those in the last two %2Newsletter%1s:
.skip 1
.begin nofill
(DE SAMEFRINGE (X Y) 
       (OR (EQ X Y)
	   (AND (NOT (ATOM X))
		(NOT (ATOM Y))
		(SAME (GOPHER X) (GOPHER Y)))))
 

(DE SAME (X Y) 
       (AND (EQ (CAR X) (CAR Y))
	    (SAMEFRINGE (CDR X) (CDR Y))))

(DE GOPHER (U) 
       (COND ((ATOM (CAR U)) U)
	     (T (GOPHER (CONS (CAAR U) (CONS (CDAR U) (CDR U))))))) 
.end

Here it is in a proposed LISP publication language:

%2samefringe[x, y] ← x %3eq %2y ∨ [¬%3at %2x ∧
¬%3at %2y ∧ same[gopher x, gopher y]]

%2same[x, y] ← %3a %2x %3eq a %3y ∧
%2samefringe[%3d %2 x, %3d %2y]

%2gopher u ← %3if at a %2u %3then%2 u
%3else%2 gopher %3aa %2u . [%3da %2u . %3d %2u]
%1
	%2gopher%1 digs up the first atom in an S-expression,
piling up the %2cdr%1 parts (with its hind legs) so that
indexing through the atoms can be resumed.  Because of shared structure,
the number of new cells in use in each argument at any time
(apart from those occupied by the original expression and assuming
iterative execution) is the number of
%2car%1s required to go from the top to the current atom -
usually a small fraction of the size of the S-expression.
If an argument of %2samefringe%1 is not elsewhere referenced,
its top level is forgotten and subject to garbage collection.

	I think this shows that %2samefringe%1 is not an example of
the need for coroutines, and a new "simplest example" should be
found.	There is no benefit in merely moving information from data
structure into control structure, and it makes some kinds of modification
harder.  Thus a game-playing algorithm that chooses the most
"cost-effective" node of the tree to extend can't have the usual simple
recursive structure.  A program with only assignments and %3go to%1s may
have the most easily modified control structure.  Of course, elegance,
understandability and a control logic admitting straightforward proofs of
correctness are also virtues.
.skip 1
.begin verbatim
John McCarthy
Artificial Intelligence Laboratory
Computer Science Department
Stanford University
Stanford, California 94305

ARPANET: MCCARTHY@SU-AI
.end

.turn on "{"
%7This draft of SAMEFR[F76,JMC]@SU-AI PUBbed at {time} on {date}.%1